package recursive;

import beans.ListNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/11
 * @verdion 1.0.0
 * 92. 反转链表 II
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * 通过次数38,082提交次数77,162
 */
public class ReverseBetween {
    public ListNode reverseBetween(ListNode head, int m, int n){
        if(head == null || m == 0){
            return head;
        }
        if(m == 1){
            head = reverse(head, n);
        } else {
            head.next = reverseBetween(head.next, --m, --n);
        }
        return head;
    }
    //TODO: 注意保存最后一个节点的下一个节点
    ListNode sucessor = null;

    private ListNode reverse(ListNode head, int n){
        if(head == null || n == 1){
            if(head != null){
                sucessor = head.next;
            }
            return head;
        }
        ListNode last = reverse(head.next, --n);
        head.next.next = head; //TODO: 这个地方会改变最后一个节点的下一个节点!!!
        head.next = sucessor;
        return last;
    }
}
